# 两数之和
def two_sum(nums: list, target: int):
    hashmap = {}
    for i, num in enumerate(nums):
        if target - num in hashmap:
            return [hashmap[target - num], i]
        hashmap[num] = i
    return []


# 三数之和
def three_sum(nums: list):
    nums.sort()
    res, set_num = [], set()
    for i in range(len(nums)):
        if i == 0 or nums[i] > nums[i - 1]:
            l, r = i + 1, len(nums) - 1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s < 0:
                    l += 1
                elif s > 0:
                    r -= 1
                else:
                    tag = f"{nums[i]}_{nums[l]}_{nums[r]}"
                    if tag in set_num:
                        l += 1
                        r -= 1
                        continue
                    res.append([nums[i], nums[l], nums[r]])
                    set_num.add(tag)
    return res


# 二分查找
def binary_search(nums: list, target: int):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1


# 选择排序
def select_sort(nums: list):
    for i in range(len(nums)):
        min_index = i
        for j in range(i + 1, len(nums)):
            if nums[j] < nums[min_index]:
                min_index = j
        nums[i], nums[min_index] = nums[min_index], nums[i]
    return nums


# 冒泡排序
def bubble_sort(nums: list):
    for i in range(len(nums)):
        for j in range(len(nums) - i - 1):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums


# 插入排序
def insert_sort(nums: list):
    for i in range(1, len(nums)):
        j, key = i - 1, nums[i]
        while j >= 0 and nums[j] > key:
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = key
    return nums


# 快速排序
def quick_sort(nums: list):
    if len(nums) <= 1:
        return nums
    pivot = nums[len(nums) // 2]
    left = [x for x in nums if x < pivot]
    middle = [x for x in nums if x == pivot]
    right = [x for x in nums if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)


def merge_sort(nums: list):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    return merge(left, right)

def merge(left: list, right: list):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# 爬楼梯和硬币问题
def climb_stairs(n: int):
    if n == 1:
        return 1
    first, second = 1, 2
    for i in range(3, n + 1):
        first, second = second, first + second
    return second


from functools import lru_cache


@lru_cache()
def climb_stairs_1(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    return climb_stairs_1(n - 1) + climb_stairs_1(n - 2)
